Algoritmo Euclideo per il MCD

L'algoritmo Euclideo per il MCD è un metodo per trovare il massimo comune divisore di due numeri, che è il numero più grande che divide entrambi senza lasciare un resto. Questo algoritmo si basa sul principio che il MCD di due numeri divide anche la loro differenza.

Descrizione dell'Algoritmo

L'algoritmo Euclideo può essere descritto utilizzando i seguenti passaggi:

1. Data una coppia di numeri interi positivi \(A\) e \(B\), con \(A \geq B\).
2. Dividi \(A\) per \(B\) e ottieni il resto \(R\). (Usa \(A \mod B\) per ottenere il resto)
3. Sostituisci \(A\) con \(B\) e \(B\) con \(R\).
4. Ripeti il processo fino a quando \(R = 0\).
5. Il MCD è il resto non nullo nell'ultimo passo in cui il resto è diverso da zero.

Rappresentazione Matematica

L'algoritmo Euclideo può essere rappresentato matematicamente come:

\[ \text{MCD}(A, B) = \begin{cases} A & \text{se } B = 0 \\ \text{MCD}(B, A \mod B) & \text{se } B \neq 0 \end{cases} \]

Esempio

Troviamo il MCD di \(252\) e \(105\) utilizzando l'algoritmo Euclideo:

1. \(A = 252\), \(B = 105\)
2. \(252 \mod 105 = 42\) (resto)
3. Sostituisci \(A\) con 105 e \(B\) con 42.
4. \(105 \mod 42 = 21\) (resto)
5. Sostituisci \(A\) con 42 e \(B\) con 21.
6. \(42 \mod 21 = 0\) (resto)

Poiché il resto è ora 0, il MCD di 252 e 105 è 21.

---

Comprendere l'Algoritmo Euclideo

L'Algoritmo Euclideo utilizza le seguenti proprietà chiave:

• \(\text{MCD}(A,0) = A\)
• Se \(A = B \cdot Q + R\) e \(B \neq 0\), allora \(\text{MCD}(A, B) = \text{MCD}(B, R)\), dove \(Q\) è un intero e \(R\) è un intero compreso tra 0 e \(B-1\)

Queste proprietà ci permettono di trovare il MCD in vari scenari. L'algoritmo riduce iterativamente problemi complessi in problemi più semplici fino a raggiungere una soluzione. Le dimostrazioni convalidano l'efficacia dell'algoritmo.

Dimostrazioni

Possiamo dimostrare la correttezza dell'algoritmo attraverso le seguenti dimostrazioni:

• Prova che \(\text{MCD}(A,0) = A\): Il numero più grande che può dividere esattamente \(A\) è \(A\). Tutti i numeri interi dividono esattamente 0, rendendo \(A\) il massimo comune divisore. \(\square\)


• Prova che \(\text{MCD}(A, B) = \text{MCD}(B, R)\) e \(\text{MCD}(A, B) = \text{MCD}(B, A)\):
  
  

  Consideriamo il \(\text{MCD}(A, B)\), dove \(A\) e \(B\) sono interi, \(R\) rappresenta il resto quando \(A\) è diviso per \(B\), espresso come \(R = A \mod B\). Questo resto \(R\) può essere calcolato come \(R = A - QB\), dove \(Q\) è il quoziente di \(A\) diviso per \(B\), o \(Q = \frac{A}{B}\).

  
  

  In questa prova, usiamo il fatto che se \(A \ | \ B\) e \(A \ | \ C\), allora \(A \ | \ (xB + yC)\). Possiamo pensarlo in questo modo: se possiamo dividere \(B\) in pezzi di \(A\) e se possiamo dividere \(C\) in pezzi di \(A\), allora possiamo dividere \(xB + yC\) in pezzi di \(A\).

  
  

  Consideriamo \( M = \text{MCD}(A, B) \) e \( N = \text{MCD}(B, R) \). Poiché \( M \) divide sia \( A \) che \( B \), deve anche dividere \( R = A - BQ \). Questo dimostra che \( M \) è un divisore comune di \( B \) e \( R \), quindi deve essere \( \leq N \), il loro massimo comune divisore. Allo stesso modo, poiché \( N \) divide sia \( B \) che \( R \), deve dividere \( A = BQ + R \), quindi \( N \leq M \). Poiché \( M \leq N \) e \( N \leq M \), abbiamo \( M = N \).

  
  

  Questo implica anche che \(\text{MCD}(A, B) = \text{MCD}(B, A)\). \(\square\)

Ora che abbiamo dimostrato la validità dell'algoritmo, dobbiamo dimostrare che l'algoritmo termina in un numero finito di passaggi.

• Prova che l'algoritmo termina in un numero finito di passaggi:
  
  

  Dato che ad ogni passo \(A\) è diviso per \(B\), il resto \(A \mod B = R\) è strettamente minore di \(B\). Ad ogni iterazione, l'algoritmo sostituisce \(A\) con \(B\) e \(B\) con \(R\). Dato che \(A \leq B\) e \(B < R\), ad ogni passo abbiamo un numero strettamente minore di \(B\). Pertanto, l'algoritmo termina in un numero finito di passaggi. \(\square\)

L'algoritmo Euclideo è uno dei più efficienti per trovare il massimo comune divisore di due numeri. È anche cruciale nell'algoritmo di crittografia RSA. Esiste anche una versione estesa dell'algoritmo che può essere trovata nell'Algoritmo Euclideo Esteso.